﻿//#define _CRT_SECURE_NO_WARNINGS
//#include<stdio.h>
//#include<assert.h>
//#include<CertExit.h>
//typedef char datatype;
//typedef struct stack {
//	datatype* a;
//	int capacity;
//	int top;
//}st;
//void stackinit(st* ps)
//{
//	assert(ps);
//	ps->a = (datatype*)malloc(sizeof(datatype) * 4);
//	if (ps->a == NULL)
//	{
//		printf("malloc?fail\n");
//		exit(-1);
//	}
//	ps->capacity = 4;
//	ps->top = 0;
//}
//void stackpush(st* ps, datatype x)
//{
//	assert(ps);
//	if (ps->top == ps->capacity)
//	{
//		datatype* cmp = (datatype*)realloc(ps->a, ps->capacity * sizeof(datatype) * 2);
//		if (cmp == NULL)
//		{
//			printf("realloc?fail\n");
//			return;
//		}
//		else
//		{
//			ps->a = cmp;
//			ps->capacity *= 2;
//		}
//	}
//	ps->a[ps->top] = x;//将值给数组
//	ps->top++;//然后栈顶个数++
//}
//void stackpop(st* ps)
//{
//	assert(ps);
//	ps->top--;
//}
//datatype popdata(st* ps)
//{
//	assert(ps);
//	assert(ps->top);
//	return ps->a[ps->top - 1];
//}
//int stackempty(st* ps)
//{
//	assert(ps);
//	return ps->top == 0;
//}
//void stackdestory(st* ps)
//{
//	assert(ps);
//	ps->capacity = ps->top = 0;
//	ps->a = NULL;
//	return;
//}
//int isValid(char* s)
//{
//	st ST;
//	stackinit(&ST);
//	while (*s != '\0')
//	{
//		switch (*s)
//		{
//		case '{':
//		case '[':
//		case '(':
//		{
//			stackpush(&ST, *s);//入栈
//			++s;
//			break;
//		}
//		case '}':
//		case ']':
//		case ')':
//		{
//			if (stackempty(&ST))
//			{
//				stackdestory(&ST);
//				return 0;
//			}
//			char top = popdata(&ST);//取上述入栈的栈顶元素
//			stackpop(&ST);//删除数据
//			//开始不匹配判断
//			if ((*s == '}' && top != '{')
//				|| (*s == ']' && top != '[')
//				|| (*s == ')' && top != '('))
//			{
//				stackdestory(&ST);
//				return 0;
//			}
//			else//匹配
//			{
//				++s;
//			}
//			break;
//		}
//		default:
//			break;
//		}
//	}
//	if (!stackempty(&ST))
//	{
//		return 0;
//	}
//	stackdestory(&ST);
//	return 1;
//}
//
//int main()
//{
//	char s[100];
//	scanf("%s", s);
//	int t=isValid(s);
//	printf("%d", t);
//	return 0;
//}

//#include<stdio.h>
//typedef struct{
//		Quene* q1;
//		Quene* q2;
//
//} MyStack;
//typedef int datatype;
//typedef struct QNode
//{
//	struct QNode  * next;
//	datatype data;
//}QNode;
//typedef struct Quene
//{
//	QNode* tail;
//	QNode* head;
//
//}Quene;
//
//void lineinit(Quene* ps)
//{
//	assert(ps);
//	ps->tail = ps->head = NULL;
//}
//void linepush(Quene* ps, int x)//队尾入
//{
//	assert(ps);
//	QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创造新的节点
//	//判断是否开辟成功
//	if (newnode == NULL) {
//		printf("malloc fail\n");
//		exit(-1);
//	}
//	newnode->data = x;
//	newnode->next = NULL;
//	if (ps->tail == NULL)
//	{
//		ps->tail = ps->head = newnode;
//	}
//	else
//	{
//		ps->tail->next = newnode;
//		ps->tail = ps->tail->next;
//	}
//
//}
//void linepop(Quene* ps)//队头删
//{
//	assert(ps);
//	assert(ps->head);
//	//一个节点
//	if (ps->head->next == NULL)
//	{
//		free(ps->head);
//		ps->tail = ps->head = NULL;
//	}
//	//俩个及俩个以上的节点
//	else
//	{
//		QNode* next = ps->head->next;
//		free(ps->head);
//		ps->head = next;
//	}
//}
//datatype linetopdata(Quene* ps)//取队头元素
//{
//	assert(ps);
//	assert(ps->head);
//	return ps->head->data;
//}
//datatype linepopdata(Quene* ps)
//{
//	assert(ps);
//	assert(ps->head);
//	return ps->tail->data;
//}
//bool lineempty(Quene* ps)
//{
//	assert(ps);
//	return ps->head == NULL;
//
//}
//datatype linesize(Quene* ps)
//{
//	assert(ps);
//	QNode* cur = ps->tail;
//	int size = 0;
//	while (cur)
//	{
//		++size;
//		cur = cur->next;
//	}
//	return size;
//}
//void linedestory(Quene* ps)
//{
//	assert(ps);
//	QNode* cur = ps->tail;
//	while (cur)
//	{
//		QNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	ps->head = ps->tail = NULL;
//}
//
//
//MyStack* myStackCreate()
//{
//	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));//开辟一个新的结构体，然后包含俩个队列。
//	if (ps == NULL)
//	{
//		printf("malloc fail\n");
//		exit(-1);
//	}
//	lineinit(&ps->q1);
//	lintinit(&ps->q2);
//	return ps;
//}
//
//void myStackPush(MyStack* obj, int x)
//{
//	//q1队列为空，则导入q2队列中
//	if (!lineempty(&obj->q1))
//	{
//		linepush(&obj->q1, x);
//	}
//	else
//		//否则将数据导入q2中
//	{
//		linepush(&obj->q2, x);
//	}
//}
//
//int myStackPop(MyStack* obj)
//{
//	//假设
//	Quene* empty = &obj->q1;//将空的队列给q1
//	Quene* nonempty = &obj->q2;//将不空的队列给q2
//	if (lineempty(&obj->q1))
//	{
//		empty = &obj->q2;
//		nonempty = &obj->q1;
//	}
//	//将数据导入不为空的队列中去，
//	while (linesize(nonempty) > 1)
//	{
//		linepush(empty, linetopdata(nonempty));//将不为空的队头数据依次放入为空的队头队列中去
//		linepop(nonempty);//给一个删一个
//	}
//	int top = linetopdata(nonempty);//取最后剩的一个数据
//	linepop(nonempty);//最后剩的一个数据删掉
//	return top;//实现了俩个数列实现栈
//}
//
//int myStackTop(MyStack* obj)//取栈顶元素
//{
//	//q1队列为空，则导入q2队列中
//	if (!lineempty(&obj->q1))
//	{
//		return linepopdata(&obj->q1);//队列的尾部元素就是栈顶元素
//	}
//	else
//		//否则将数据导入q2中
//	{
//		return linepopdata(&obj->q2);//队列的尾部元素就是栈顶元素
//	}
//}
//
//bool myStackEmpty(MyStack* obj)
//{
//	return lineempty(&obj->q1) && lineempty(&obj->q2);
//}
//
//void myStackFree(MyStack* obj)
//{
//	linedestory(&obj->q1);
//	linedestory(&obj->q2);
//	free(obj);
//}



